import java.util.HashMap;

public class LRUCache {

    static class LRUNode {
        int key;
        int val;
        LRUNode prove;
        LRUNode next;
        public LRUNode() {

        }
        public LRUNode(int key,int val) {
            this.key = key;
            this.val = val;
            prove = null;
            next = null;
        }

        @Override
        public String toString() {
            return "{" +"key=" + key +", val=" + val + "}  ";
        }
    }

    public HashMap<Integer,LRUNode> cache;
    public int usedSize;// 当前已经存储的有效长度
    public int size_default;// 设置的LRU默认长度
    public  LRUNode head;// 头结点
    public LRUNode tail;// 尾巴节点
    public LRUCache(int size_default) {
        cache = new HashMap<>();
        head = new LRUNode();
        tail = new LRUNode();
        head.next = tail;
        tail.prove = head;
        this.size_default = size_default;
    }

    public void put(int key,int val) {
        LRUNode ret = cache.get(key);
        if(ret == null) {
            // 不是空
            // 1.实例化一个节点
            LRUNode node = new LRUNode(key,val);
            // 1.2 添加到hashMap 当中
            cache.put(key,node);
            // 添加到尾巴
            addToNode(node);
            usedSize++;
            if(usedSize > size_default) {
                // 当前的节点数量 大于默认的节点数量，
                removeNode();
            }
        }else {
            // 当前节点已存在，更新节点的val值
            ret.val = val;
            // 将节点删除
            removeToNode(ret);
            // 重新添加尾部
            addToNode(ret);
        }
    }

    /**
     * 删除节点
     * @param ret
     */
    private void removeToNode(LRUNode ret) {
        ret.prove.next = ret.next;
        ret.next.prove = ret.prove;
    }

    /**
     * 将节点从尾部删除
     */
    private void removeNode() {
        head.next = head.next.next;
        head.next.prove = tail;
        usedSize--;
    }

    /**
     * 将节点添加到尾巴
     * @param node
     */
    private void addToNode(LRUNode node) {
        // 添加到尾巴
        node.prove = tail.prove;
        node.prove.next = node;
        node.next = tail;
        tail.prove = node;
    }

    /**
     * 查看key是否存在
     * @param key
     * @return
     */
    public int get(int key) {
        LRUNode ret = cache.get(key);
        if(ret == null) {
            return -1;
        }
        removeToNode(ret);
        addToNode(ret);
        return ret.val;
    }

    /**
     * 打印节点
     */
    public void print() {
        LRUNode cur = head.next;
        while(cur != tail) {
            System.out.print(cur);
            cur = cur.next;
        }
        System.out.println();
    }
}
